package com.bigshen.algorithm.bStack.solution02MinStack;

import java.util.Stack;

/**
 * 155. Min Stack
 * Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
 *
 * push(x) -- Push element x onto stack.
 * pop() -- Removes the element on top of the stack.
 * top() -- Get the top element.
 * getMin() -- Retrieve the minimum element in the stack.
 *  
 *
 * Example 1:
 *
 * Input
 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
 * [[],[-2],[0],[-3],[],[],[],[]]
 *
 * Output
 * [null,null,null,null,-3,null,0,-2]
 *
 * Explanation
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.getMin(); // return -3
 * minStack.pop();
 * minStack.top();    // return 0
 * minStack.getMin(); // return -2
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-stack
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 执行用时：8 ms, 在所有 Java 提交中击败了40.44%的用户
 * 内存消耗：9.9 MB, 在所有 Java 提交中击败了97.30%的用户
 *
 */
public class MinStack02 {

    Stack<Integer> stack = null;
    Stack<Integer> minStack = null; // 使用一个辅助的最小栈，当插入元素比minStack栈顶元素大时，直接插入minStack栈顶元素，出栈时两个栈同时出

    /** initialize your data structure here. */
    public MinStack02() {
        stack = new Stack();
        minStack = new Stack();
    }

    public void push(int x) {
        stack.push(x);
        if (!minStack.isEmpty()) {
            Integer min = minStack.peek();
            if (min > x) {
                // 插入x元素比minStack栈顶元素大时，直接插入minStack栈顶元素
                minStack.push(x);
            } else {
                // 插入x元素比minStack栈顶元素小时，插入x元素
                minStack.push(min);
            }
        } else {
            minStack.push(x);
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

}
